import java.util.ArrayList;
import java.util.List;

/**
 * 1859. 将句子排序
 * https://leetcode-cn.com/problems/sorting-the-sentence/
 */
public class Solutions_1859 {
    public static void main(String[] args) {
        String s1 = "is2 sentence4 This1 a3";  // output: "This is a sentence"
        String s2 = "Myself2 Me1 I4 and3";  // output: "Me Myself and I"

        List<String> inputs = new ArrayList<>();
        inputs.add(s1);
        inputs.add(s2);

        for (String input : inputs) {
            String result = sortSentence(input);
            System.out.println(result);
        }
    }

    public static String sortSentence(String s) {
        String[] sarr = s.split(" ");
        int len = sarr.length;
        // 结果数组
        String[] strs = new String[len];
        // 结果字符串
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < sarr.length; i++) {
            // 通过最后一个字符，计算得到对应的下标
            String str = sarr[i];
            char index = str.charAt(str.length() - 1);
            int idx = index - '0' - 1;

            // 保存字符串到相应下标，同时删除数字
            strs[idx] = str.substring(0, str.length() - 1);
        }
        // 拼接字符串
        for (String str : strs) {
            sb.append(" ");
            sb.append(str);
        }
        String res = sb.substring(1);
        return res;
    }
}
